#include <stdio.h>
#include <stdlib.h>

typedef struct Tree {
	int data;
	struct Tree *left;
	struct Tree *right;
	int lTag;
	int rTag;
} tree;

tree *pre = NULL;

tree* add(tree *t, int data) {
	if (t == NULL) {
		t = (tree *) malloc(sizeof(tree));
		t->data = data;
		t->left = NULL;
		t->right = NULL;
		t->lTag = 0;
		t->rTag = 0;
	} else if (t->data > data) {
		t->left = add(t->left, data);
	} else
		t->right = add(t->right, data);
	return t;
}

tree* array_to_tree(int *arr, int len) {
	int i;
	tree *t = add(NULL, *arr);
	for (i = 1; i < len; i++)
		add(t, *(arr+i));
	return t;
}

void thread_tree(tree *p) {
	if (p != NULL) {
		thread_tree(p->left);
		if (p->left == NULL) {
			p->left = pre;
			p->lTag = 1;
		}
		if (pre != NULL && pre->right == NULL) {
			pre->right = p;
			pre->rTag = 1;
		}
		pre = p;
		thread_tree(p->right);
	}
}

void traversal(tree *root) {
	tree *p = root;
	while (p->left != NULL) 
		p = p->left;
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->right;
	}
	printf("\n");
}

void main() {
	int a[] = {40, 20, 30, 10, 60, 50, 70};
	tree *root = array_to_tree(a, 7);
	thread_tree(root);
	traversal(root);
}
